#leetcode题目47：全排列ii
#难度：中等
#时间复杂度：O(n!)
#空间复杂度：O(n!)
#方法：回溯

# 回溯算法，注意去重，就是保证在同一个深度，不要选同样的元素

from typing import List
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        
        def dfs(visited,nums,res,path,depth):
            if depth==len(nums):
                res.append(path[:])
            for i in range(len(nums)):
                if i>0 and nums[i-1]==nums[i] and not visited[i-1]:
                    continue
                if not visited[i]:
                    visited[i]=True
                    path.append(nums[i])
                    dfs(visited,nums,res,path,depth+1)
                    path.pop()
                    visited[i]=False

        visited=[False]*len(nums)
        res=[]
        path=[]
        nums.sort()
        dfs(visited,nums,res,path,0)
        return res

#测试数据
nums=[1,1,2]
#预期输出：[[1,1,2],[1,2,1],[2,1,1]]
solution=Solution()
print(solution.permuteUnique(nums))

nums=[1,2,3]
#预期输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
solution=Solution()
print(solution.permuteUnique(nums))